#include <iostream>
#include <vector>
#include <climits>
#include <fstream>
#include <sstream>
#include <string>
#include <unordered_map>
using namespace std;

unordered_map<string, pair<int, int>> memo; // 记忆化存储

pair<int, int> matrixChainOrderHelper(const vector<int> &dims, int i, int j)
{
  if (i == j)
  {
    return {0, i}; // 单个矩阵，乘法次数为0
  }

  string key = to_string(i) + "," + to_string(j);
  if (memo.find(key) != memo.end())
  {
    return memo[key]; // 如果已经计算过，直接返回
  }

  int min_cost = INT_MAX;
  int best_split = -1;

  for (int k = i; k < j; k++)
  {
    auto left = matrixChainOrderHelper(dims, i, k);
    auto right = matrixChainOrderHelper(dims, k + 1, j);

    int current_cost = left.first + right.first + dims[i - 1] * dims[k] * dims[j];

    if (current_cost < min_cost)
    {
      min_cost = current_cost;
      best_split = k;
    }
  }

  memo[key] = {min_cost, best_split};
  return {min_cost, best_split};
}

string buildOptimalParens(const vector<int> &dims, int i, int j)
{
  if (i == j)
  {
    return to_string(i - 1); // 修正为0-based索引
  }

  string key = to_string(i) + "," + to_string(j);
  auto result = memo.at(key); // 获取最优分割点
  int split = result.second;

  return "(" + buildOptimalParens(dims, i, split) + "," + buildOptimalParens(dims, split + 1, j) + ")";
}

int main()
{
  vector<int> dims;
  string fileName = "../data/matrix_chain-github-input_03.txt";
  ifstream inputFile(fileName);
  if (!inputFile)
  {
    cerr << "无法打开文件: " << fileName << endl;
    return 1;
  }

  int numMatrices;
  inputFile >> numMatrices; // 读取矩阵数量

  int rows, cols;
  inputFile >> rows >> cols; // 读取第一个矩阵的维度
  dims.push_back(rows);
  dims.push_back(cols);

  for (int i = 1; i < numMatrices; i++)
  {
    inputFile >> rows >> cols;
    dims.push_back(cols); // 只需存储前一个矩阵的列和当前矩阵的列
  }

  inputFile.close();

  if (dims.size() < 2)
  {
    cerr << "错误: 矩阵维度数据不足" << endl;
    return 1;
  }

  // 使用分治算法（带记忆化）计算最优解
  auto result = matrixChainOrderHelper(dims, 1, dims.size() - 1);
  int min_cost = result.first;

  cout << "最优标量乘法次数: " << min_cost << endl;
  cout << "最优括号化方案: " << buildOptimalParens(dims, 1, dims.size() - 1) << endl;

  return 0;
}